In the field of data communications, data is often transmitted from one node (station) to another through a network of nodes that operate using their own independent clocks. Use of independent clocks in the nodes requires a system for ensuring that data corruption will not occur when frames of data are transmitted from a source node to a destination node through a number of repeater nodes. One method commonly employed for preventing data corruption in such networks is the use of an elasticity buffer at each node.
An elasticity buffer is a first-in first-out storage device including a number of storage elements. In the elasticity buffer, bytes of data enter and exit at different rates corresponding to the different frequency of the clock used by the upstream transmitting node compared with the local clock frequency used in the receiving node. Elasticity buffers are required even though data transfer rates are nominally the same because independent clocks in the nodes will differ in frequency by some known tolerance.
Data is stored in the elasticity buffer as it arrives from an upstream node, and is removed from the buffer for transmission to a downstream node at a rate determined by a local clock in the node. If the local clock for the node is slower than that of the upstream node, the buffer will become more and more full as the bytes in a frame are transmitted through the node. If the local clock is faster than that of the upstream node, the buffer gradually empties of all data.
The elasticity buffer in a repeater node between a source node and a destination node must include enough storage elements to ensure it will not become full before the last byte in a frame has been transmitted to a downstream node. If the buffer fills before the repeater node has transmitted the last byte to the downstream node, the buffer cannot store additional bytes being transmitted from an upstream node without corrupting previously received data that has not yet been transmitted to the downstream node.
Furthermore, there must be a minimum delay at the beginning of a frame before the elasticity buffer in the repeater node begins to output the first byte received from the upstream node. Without such an initial delay, a repeater node with a relatively fast clock will empty its elasticity buffer and will attempt to transmit bytes to the downstream node before they have been received from the upstream node. Therefore, it is important for the elasticity buffer to be "recentered" at the beginning of transmission of every frame to maintain the necessary delay that will prevent this from occurring.
These principles apply to various types of wide and local area networks, including any packet data network which connects many repeater nodes that involves point-to-point clocking. Examples include nodes connected to a token ring network or to an Ethernet network connected with multiple repeaters.
A ring network consists of a set of nodes (stations) logically connected as a serial string of nodes and transmission media to form a closed loop. Information is transmitted sequentially, as a stream of suitably encoded symbols, from one active node to the next. Each node generally regenerates and repeats each symbol and serves as the means for attaching one or more devices to the network for the purpose of communicating with other devices on the network.
A network of particular applicability is the fiber distributed data interface (FDDI), which is a proposed American National Standard for a 100 megabit per second token ring using an optical fiber medium. The characteristics of FDDI networks are described in detail by Floyd E. Ross in "FDDI--A Tutorial," IEEE Communications Magazine, Vol. 24, No. 5, pp. 10-17 (May 1986), which is hereby incorporated by reference.
Information is transmitted on an FDDI ring network in frames using a four of five group code, with each 5-bit code group being called a symbol. Of the 32 member symbol set, 16 are data symbols each representing four bits of ordered binary data, three are used for starting and ending delimiters, two are used as control indicators, and three are used for line-state signaling recognized by physical layer hardware. Each byte corresponds to two symbols or ten bits. (The term byte is used throughout the specification as a convenient way to refer to a unit of data; the functioning of the invention is not limited to any particular data unit, and other units of data, such as symbols and bits, are not excluded.)
The data transmission rate is 100 megabits per second for FDDI. A 125 megabaud transmission rate is required because of the use of a four-of-five code on the optical fiber medium. The nature of the clocking limits data frames to a maximum length of 4,500 bytes i.e., 9,000 symbols or 45,000 bits). An FDDI network consists of a theoretically unlimited number of connected nodes.
In FDDI networks, every transmission of a frame is preceded by a preamble field, which consists of idle line-state bytes (symbols). In FDDI, an idle line-state symbol corresponds to the 5-bit code group 11111. At the beginning of the frame, the preamble field of idle bytes is followed by a starting delimiter field, which consists of a two-symbol sequence JK that is uniquely recognizable independent of previously established symbol boundaries. The starting delimiter field establishes the symbol boundaries for the content that follows. The 5-bit code group corresponding to the symbol J is 11000, and the code group corresponding to the symbol K is 10001.
In an FDDI ring, a media access control entity in each node recognizes idle bytes as a preamble preceding a frame. Although it is possible to design a network in which no gap at all is provided between frames, in reality, designers of devices connected to the network prefer to have a preamble including one or more idle bytes separating each frame. The use of the preamble provides each node with a certain amount of time to recover from the preceding frame before having to respond to a subsequent frame. For example, this time period can be used for recentering the elasticity buffer in the node.
In an FDDI network, when a frame is generated in a source node and transmitted to the first downstream node, the frame will have a preamble including eight idle bytes. Furthermore, the standard for FDDI rings provides that the media access control entity in a repeater node is not required to recognize any frame having a preamble that is smaller than six idle bytes in length.
For FDDI, the nominal clock rate is 125 megahertz but a frequency tolerance of plus or minus 0.005% is allowed. The maximum frame size is 4,500 bytes. Given these constraints, it is readily understood that passage of a single frame may result in the elasticity buffer in a repeater node filling or emptying at the rate of 4.5 bits per frame because of the maximum possible difference in clock frequencies in consecutive nodes in the network.
As has been described previously, the elasticity buffer in each node in a network compensates for any differences in rates of the clocks for consecutive nodes in the network. When recentering of the elasticity buffer occurs before a subsequent frame is repeated by a node, the node will either insert or delete bytes from the total number of bytes it transmits to the downstream node, depending on whether the clock in the upstream node is slower or faster than the local clock for the node. By providing a preamble before each frame including at least a minimum number of idle bytes, the elasticity buffer can be recentered without any loss of data by only allowing addition or deletion of idle bytes in the preamble separating every pair of frames.
Therefore, in order to prevent allowable clock frequency differences from causing the elasticity buffer in a node from completely filling or emptying, the repeater node recenters its elasticity buffer by either expanding or shrinking the size of the preamble for the subsequent frame. Thus, one idle byte may be inserted in a preamble by a fast repeater node when it recenters to prevent its elasticity buffer from emptying, while one idle byte may be deleted by a slow repeater node when it recenters its elasticity buffer in order to prevent it from filling.
However, a significant problem arises when a repeater node recenters its elasticity buffer without regard to the number of idle bytes contained in the preamble for the subsequent data frame. If a minimum number of idle bytes do not separate the end of the preceding data frame from the start (i.e., the starting delimiter) of the subsequent data frame, downstream nodes in the network are not required to recognize the frame. As a result, there is a loss of data. Therefore, frames of data are lost in a network in which some method or apparatus is not provided for maintaining an interframe gap. Even when the minimum number of idle bytes separating frames is zero, deletion of bytes by the node must be limited to prevent two frames from actually colliding with each other.
Thus, in a series of nodes with randomly distributed clocks, some nodes will occasionally delete idle bytes from a preamble in order to recenter an elasticity buffer that fills too rapidly. If the nodes in the network ignore the size of the preamble when they delete idle bytes, a number of idle bytes between a particular pair of frames may be deleted, making it impossible for a downstream node to repeat the second frame and continue the transmission.
The probability at which frame loss occurs due to the preamble not containing a minimum number of idle bytes depends on several factors: (1) the most critical factor is the size of the units in which idles are added or deleted by the nodes to the preamble between two frames (i.e., in units of bytes, symbols, or bits); (2) the number of nodes in the network; (3) the minimum number of idle bytes required by each repeater node in order to recognize a subsequent frame; and (4) the distribution of clock speeds.
Analysis has shown that it is possible for half of all maximum length frames to be lost by a fifth repeater node in a situation where clocks in an FDDI ring alternate between the minimum and minimum allowable speeds, idles are added or deleted from the preamble in units of bytes, the nodes require a minimum of six idle bytes between frames, and the size of the original preamble is eight idle bytes. An illustration of the problem is shown in Table I, which lists the number of idle bytes remaining between frames as the frames are transmitted from node 1 to node 6. The relatively fast nodes must add an idle byte every two maximum length frames, whereas the relatively slow stations must delete an idle byte every two maximum length frames. The preambles transmitted from a number of nodes could therefore follow the following pattern:
TABLE I ______________________________________ Frame: 1 2 3 4 5 ______________________________________ Node 1 (fast) 8 8 8 8 8 Node 2 (slow) 8 7 8 7 8 Node 3 (fast) 9 7 9 7 9 Node 4 (slow) 9 6 9 6 9 Node 5 (fast) 10 6 10 6 10 Node 6 (slow) 10 5 10 5 10 ______________________________________
This example shows that downstream nodes may reject the second and fourth frames because those frames contain inadequate preambles, including only five idle bytes between frames.
In a situation in which: (1) idles are added or deleted in units of symbols; (2) there is a pseudo-random distribution of clock frequencies among nodes; (3) there are 101 nodes; (4) the minimum required number of idle symbols between frames is twelve; and (5) frames having the maximum length of 9,000 symbols are being transmitted; a simulation of the problem revealed that there was a probability that more than one out of ten frames would be lost.
Generally, this problem with the operation of elasticity buffers is related to the shrinking of preambles due to cumulative roundoff error. When an FDDI source node creates a frame, it is transmitted with a preamble of eight idle bytes (16 idle symbols). The network has a maximum frame size of 4,500 bytes and a clock tolerance of plus or minus 0.005%, so that a node will have to add or delete no more than 4.5 bits when it recenters its elasticity buffer following transmission of a frame. Although this slippage of 4.5 bits reflects the maximum clock frequency differences from the nominal frequency for all stations in the network, this does not prevent preambles from falling outside the predicted range of 75.5 to 84.5 bits. Nodes do not add or delete fractions of bits from frames repeated to downstream nodes because of the technical complexity and the resulting addition to the jitter seen at the downstream node due to a frequency shift for the duration of one bit. Instead, the node rounds the number of bits it adds or deletes to the nearest whole bit, and these roundoff errors can accumulate along the network. In the worst case, a preamble of 80 bits can shrink to nothing after being repeated by 80 nodes.
However, the scenario described in the preceding paragraph is extremely unlikely. Although the maximum roundoff error is almost one bit, the average roundoff error per node is about 0.25 bits, and the direction of the error is random. Therefore, cumulative roundoff error is best estimated as a random walk with a step of 0.25 bits per node. For a ring having 1,000 nodes, this results in a one in 2,000,000 probability that a preamble will randomly walk to zero bits.
Unfortunately, the problem of shrinking preambles is made much more likely by two factors. First, standards for nodes connected to a network such as FDDI do not specify a maximum roundoff error, and designers therefore plan implementations of nodes that round to the nearest byte (10 bits) or symbol (5 bits). This increases the size of each step in the random walk, thereby dramatically increasing the probability of collisions between consecutive frames. Second, as discussed above, standards for certain networks may not require that the repeater node process frames preceded by a preamble including less than a relatively large number of idle bytes or symbols (e.g., six bytes for FDDI). Thus, designers of nodes to be connected to an FDDI network are relying on a six byte preamble of idles being preserved with high probability. This means that only one-quarter of the initial preamble of eight bytes for an DDI network is available for shrinkage due to recentering of the elasticity buffers in a number of nodes.
A process is thus required which can be reasonably be implemented and which will have an acceptable frame loss range for networks containing a large number of nodes. The consensus in the industry is that a frame loss rate of one frame in 10 billion is acceptable for 1000 nodes connected in an FDDI network.
Thus, there is a need for a method and apparatus for avoiding unnecessary shrinkage of a gap between two frames when a number of nodes in a network recenter their elasticity buffers.